Linear Search vs. Binary Search

Manual Big-O Analysis

linear_search

Static analysis of `linear_search`: - Recursion: no - Max loop nesting depth: 1 - Divide-and-conquer hints: no **Estimated Time Complexity:** O(n) **Estimated Space Complexity:** O(1) Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.

binary_search

Static analysis of `binary_search`: - Recursion: no - Max loop nesting depth: 1 - Divide-and-conquer hints: yes **Estimated Time Complexity:** O(n) **Estimated Space Complexity:** O(1) Why: One level of looping detected; typical single pass suggests O(n) time and O(1) space. These are heuristics; empirical results below provide a practical check.

Beginner-friendly Summary

linear_search When the input size n doubles, the runtime grows by approximately 2.08×, which suggests performance closer to O(n).

binary_search When the input size n doubles, the runtime grows by approximately 1.09×, which suggests performance closer to O(log n).

Interview-style Summaries

linear_search linear_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
binary_search binary_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.

Runtime Benchmarks

Table (mean ± 95% CI)

n	linear_search	binary_search
1000	15.46 µs ± 6.87 µs	1.72 µs ± 130.18 ns
2000	28.77 µs ± 11.52 µs	1.84 µs ± 131.06 ns
4000	56.89 µs ± 22.32 µs	2.03 µs ± 218.72 ns
8000	129.09 µs ± 64.29 µs	2.17 µs ± 122.59 ns
16000	196.70 µs ± 100.18 µs	2.63 µs ± 409.94 ns
32000	543.67 µs ± 181.70 µs	2.59 µs ± 292.80 ns

Peak Memory (per call)

Table (mean ± 95% CI)

n	linear_search	binary_search
1000	211.64 B ± 18.98 B	170.91 B ± 7.61 B
2000	226.91 B ± 11.34 B	181.09 B ± 7.61 B
4000	232.00 B ± 0.00 B	196.36 B ± 8.79 B
8000	232.00 B ± 0.00 B	193.82 B ± 9.49 B
16000	232.00 B ± 0.00 B	201.45 B ± 5.67 B
32000	232.00 B ± 0.00 B	204.00 B ± 0.00 B

Comparison Summary

Best/worst runtime per n (lower is better). Mean ranks aggregate performance across all n.

n	Best Runtime	Worst Runtime	Mean Ranks
1000	binary_search	linear_search	linear_search: 2.00 binary_search: 1.00
2000	binary_search	linear_search	linear_search: 2.00 binary_search: 1.00
4000	binary_search	linear_search	linear_search: 2.00 binary_search: 1.00
8000	binary_search	linear_search	linear_search: 2.00 binary_search: 1.00
16000	binary_search	linear_search	linear_search: 2.00 binary_search: 1.00
32000	binary_search	linear_search	linear_search: 2.00 binary_search: 1.00

Methods

Methods: - **Runtime** measured with `time.perf_counter()`; each (function, n) pair ran 11 times after 2 warmup iterations. GC was enabled and collected before runs. - **Memory** peak measured with `tracemalloc` backend (`tracemalloc` by default). - **Confidence Intervals:** T at 95% confidence. T-intervals use standard t critical values; bootstrap uses 2,000 resamples with a fixed seed. - **Reference curves** (O(1), O(log n), O(n), O(n log n), plus any custom) were normalized at the largest n to match the average observed runtime scale.